import java.util.HashSet;
import java.util.Objects;
import java.util.Random;
import java.util.Set;

public class Graph {
    //链式前向星
    public Edge[] edges ;
    public int[] head ;
    public int cnt  ;
    public int[] nodeColor ;
    public int colorNub ;

    Graph(int n,int maxNub,int colorNub){
        edges = new Edge[maxNub*2]  ;
        head = new int[n] ;
        cnt = 0 ;
        for (int i=0;i<n;i++){
            head[i] = -1 ;
        }
        bulidGraph(n,maxNub) ;
        this.colorNub = colorNub ;
        nodeColor = new int[n] ;
    }

    void addEdge(int u,int v){
        Edge edge = new Edge() ;
        edge.to = v ;
        edge.next = head[u];
        edges[cnt] = edge ;
        head[u] = cnt ;
        cnt++;
    }

    public void printNodeColor(){
        for(int i=0;i<nodeColor.length;i++){
            System.out.println("点_"+i+"_的颜色是_"+nodeColor[i]+"_");
        }
    }

    public void printGraph(){
        int cnt = 1 ;
        for(int i=0;i<head.length;i++){
            for(int j=head[i];j!=-1;j=edges[j].next){
                //在之前的都不用输出
                if(edges[j].to>i){
                    System.out.println(cnt+": "+i+"<----->"+edges[j].to);
                    cnt++ ;
                }
            }
        }
        System.out.println("\n");
    }

    public boolean[] getAroundColors(int point){
        boolean[] colors = new boolean[colorNub+1] ;
        for(int i=head[point];i!=-1;i=edges[i].next){
            int to = edges[i].to ;
            colors[nodeColor[to]] = true ;
        }
        return colors ;
    }

    //链式前向星不能有相同的边出现
    void bulidGraph(int n,int maxNub){
        Set<Pair> edgeSet = new HashSet<>();
        Random random = new Random() ;
        //首先整一颗树出来 n-1条边
        int to ;
        for(int i=1;i<n;i++){
            to = random.nextInt(i);
            edgeSet.add(new Pair(to,i));
        }
        maxNub = maxNub-n+1 ;
        for(int i=0;i<maxNub;i++){
            //随便选两个点出来加边进去
            int a = random.nextInt(n);
            int b = random.nextInt(n);
            int s = Math.min(a,b) ;
            int l = Math.max(a,b) ;
            edgeSet.add(new Pair(s,l));
        }

        for (Pair temp : edgeSet) {
            addEdge(temp.a, temp.b);
            addEdge(temp.b, temp.a);
        }

    }
}

class Edge{
    int next ;
    int to ;
}

class Pair{
    int a ;
    int b ;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Pair pair = (Pair) o;
        return a == pair.a && b == pair.b;
    }

    @Override
    public int hashCode() {
        return Objects.hash(a, b);
    }

    Pair(int a, int b){
        this.a = a ;
        this.b = b ;
    }

}
